package com.wu.leetcode.sort.bubblesort;

import java.util.Arrays;

/**
 * @author lynn
 * @date 2020/7/11 - 22:18
 * 通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，
 * 若发现逆序则交换，使值较大的元素逐渐从前移向后部
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] array = {3, 9, -1, 10, -2};
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 如果一趟比较下来没有进行过交换，就说明序列有序，
     * 因此要在排序过程中设置一个标志flag判断元素是否进行过交换
     * @param array 待排序的数组
     */
    public static void bubbleSort(int[] array) {
        //用于交换数据
        int temp = 0;
        // 用来标志排序过程中是否有交换
        boolean flag = false;
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    //有交换
                    flag = true;
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
            if (!flag) {
                break;//没有过交换
            } else {
                //重置！！！！ 每次循环都会进行判断
                flag = false;
            }
        }
    }
}
